package com.ocean.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/cousins-in-binary-tree/
 * <p>
 * 二叉树的堂兄弟节点
 * <p>
 * 在同一深度 但父节点不同
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/14 <br>
 */
public class CousinsInBinaryTree {

    public static void main(String[] args) {
        CousinsInBinaryTree cousinsInBinaryTree = new CousinsInBinaryTree();
        System.out.println(cousinsInBinaryTree.isCousins(TreeNode.getRoot(),2,3));
        System.out.println(cousinsInBinaryTree.isCousins(TreeNode.getRoot(),4,6));
    }

    /**
     * 广度优先
     *
     * @param root
     * @param x
     * @param y
     * @return
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        TreeNode xP = null;
        TreeNode yP = null;
        while (!deque.isEmpty()) {
            int size = deque.size();
            // 表示在同一层
            boolean foundX = false;
            boolean foundY = false;
            for (int i = 0; i < size; i++) {
                TreeNode p = deque.poll(); // 父类
                TreeNode left = p.getLeft();
                TreeNode right = p.getRight();
                if (left != null) {
                    deque.offer(left);
                    if (left.getValue() == x) {
                        foundX = true;
                        xP = p;
                    }
                    if (left.getValue() == y) {
                        foundY = true;
                        yP = p;
                    }
                }

                if (right != null) {
                    deque.offer(right);
                    if (right.getValue() == x) {
                        foundX = true;
                        xP = p;
                    }
                    if (right.getValue() == y) {
                        foundY = true;
                        yP = p;
                    }
                }
            }
            if (foundX || foundY) {
                // 任何一个找到了
                return foundX == foundY && xP != yP;
            }
        }
        // 都没找到
        return false;
    }


}
